#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<iostream>
using namespace std;

//vector<vector<int>> ret;
//vector<int> path;
//
//void dfs(vector<int>& nums, int i)
//{
//    if (i == nums.size())
//    {
//        ret.push_back(path);
//        return;
//    }
//
//    path.push_back(nums[i]);
//    dfs(nums, i + 1);
//    path.pop_back();
//
//    dfs(nums, i + 1);
//}
//int subsetXORSum(vector<int>& nums) {
//    dfs(nums, 0);
//    int ans = 0;
//    for (int i = 0; i < ret.size(); i++)
//    {
//        if (ret[i].empty()) continue;
//        int tmp = ret[i][0];
//        for (int j = 1; j < ret[i].size(); j++)
//        {
//            tmp ^= ret[i][j];
//        }
//        ans += tmp;
//    }
//    return ans;
//}


//int ret;
//int tmp = 0;
//
//void dfs(vector<int>& nums, int i, int tmp)
//{
//    if (i == nums.size())
//    {
//        ret += tmp;
//        return;
//    }
//
//    dfs(nums, i + 1, tmp ^ nums[i]);
//
//    dfs(nums, i + 1, tmp);
//}
//int subsetXORSum(vector<int>& nums) {
//    dfs(nums, 0, tmp);
//    return ret;
//}

//
//vector<vector<int>> ret;
//bool check[8];
//vector<int> path;
////void dfs(vector<int>& nums)
////{
////    if (path.size() == nums.size())
////    {
////        ret.push_back(path);
////        return;
////    }
////
////    for (int i = 0; i < nums.size(); i++)
////    {
////        if (check[i] == false)
////        {
////            path.push_back(nums[i]);
////            check[i] = true;
////            dfs(nums);
////            check[i] = false;
////            path.pop_back();
////        }
////    }
////}
////vector<vector<int>> permuteUnique(vector<int>& nums) {
////    dfs(nums);
////    vector<vector<int>> tmp;
////    tmp.push_back(ret[0]);
////    for (int i = 1; i < ret.size(); i++)
////    {
////        int flag = 0;
////        for (int j = 0; j < tmp.size(); j++)
////        {
////            if (ret[i] == tmp[j]) flag = 1;
////        }
////        if (flag == 0) tmp.push_back(ret[i]);
////    }
////    return tmp;
////}
//
//void dfs(vector<int>& nums)
//{
//    if (path.size() == nums.size())
//    {
//        ret.push_back(path);
//        return;
//    }
//
//    for (int i = 0; i < nums.size(); i++)
//    {
//        if (i > 0 && nums[i] == nums[i - 1]) continue;
//        if (check[i] == false)
//        {
//            path.push_back(nums[i]);
//            check[i] = true;
//            dfs(nums);
//            check[i] = false;
//            path.pop_back();
//        }
//    }
//}
//vector<vector<int>> permuteUnique(vector<int>& nums) {
//    sort(nums.begin(), nums.end());
//    dfs(nums);
//    return ret;
//}

vector<string> ret;
string path;
bool check[26];
void dfs(unordered_map<char, string> hash, string digits, int pos, int i)
{
    if (path.size() == digits.size())
    {
        ret.push_back(path);
        return;
    }

    for (int j = 0; j < hash[digits[i]].size(); j++)
    {
        path.push_back(hash[digits[i]][j]);
        check[hash[digits[i]][j] - 'a'] = true;
        dfs(hash, digits, digits[i + 1] - '0', i + 1);
        path.pop_back();
        check[hash[digits[i]][j] - 'a'] = false;
    }

}
vector<string> letterCombinations(string digits) {
    unordered_map<char, string> hash{
    {'0', " "}, {'1',"*"}, {'2', "abc"},
    {'3',"def"}, {'4',"ghi"}, {'5',"jkl"},
    {'6',"mno"}, {'7',"pqrs"},{'8',"tuv"},
    {'9',"wxyz"} };

    dfs(hash, digits, 0, 0);
    return ret;
}

int main()
{
    vector<int> v{ 1,1,2 };
    //subsetXORSum(v);
    //permuteUnique(v);
    vector<string> sv{ "23" };
    letterCombinations("23");

	return 0;
}